package com.origin.niuke.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/8/10 21:50
 * 数据流中的中位数
 * 算法：堆、插入排序
 */
public class BM48 {

    public static class Solution {
        // 存储中位数左边的数
        PriorityQueue<Integer> min = new PriorityQueue<>();
        // 存储中位数右边的数
        PriorityQueue<Integer> max = new PriorityQueue<>((a, b) -> b - a);

        public void Insert(Integer num) {
            min.offer(num);
            max.offer(min.poll());
            if (min.size() < max.size()) min.offer(max.poll());
        }

        public Double GetMedian() {
            if (min.size() == max.size()) return (double) (min.peek() + max.peek()) / 2;
            else return (double) min.peek();
        }

    }

    public static class SolutionChaRu {

        List<Integer> list = new ArrayList<>();

        public void Insert(Integer num) {
            int i = 0;
            for (; i < list.size(); i++) if (num > list.get(i)) break;
            list.add(i, num);
        }

        public Double GetMedian() {
            int size = list.size();
            if (size % 2 == 0) return (double) (list.get(size / 2) + list.get(size / 2 - 1)) / 2;
            else return (double) list.get(size / 2);
        }

    }

}
